This patent specification discloses subject matter which is disclosed and claimed in co-owned applications U.S. Pat. No. 5,706,299 issued Jan. 6, 1998 (Baydar et al., application number Ser. No. 887, 348 filed May 21, 1992, entitled xe2x80x9cSONET TRIBUTARY AMBIGUITY RESOLUTION FOR ELASTIC STORE CONTROLxe2x80x9d); U.S. Pat. No. 5,740,157 issued Apr. 14, 1998 (Demiray et al., application number Ser. No. 887,156 filed May 21, 1992, entitled xe2x80x9cDISTRIBUTED CONTROL METHODOLOGY AND MECHANISM FOR IMPLEMENTING AUTOMATIC PROTECTION SWITCHINGxe2x80x9d); U.S. Pat No. 5,715,248 issued Feb. 3, 1998 (Lagle, III et al., application Ser. No. 886,723 filed May 21, 1992, entitled xe2x80x9cDERIVATION OF VT GROUP CLOCK FROM SONET STS-1 PAYLOAD CLOCK AND VT GROUP BUS DEFINITIONxe2x80x9d); U.S. Pat. No. 5,872,780 issued Feb. 16, 1999 (Demiray et al., application Ser. No. 886,724 filed May 21, 1992, entitled xe2x80x9cSONET DATA TRANSFER PROTOCOL BETWEEN FACILITY INTERFACES AND CROSS-CONNECTxe2x80x9d); and U.S. Pat No. 5,809,032 issued Sep. 15, 1998 (Weeber et al., application Ser. No. 783,197 filed Jan. 15, 1997, entitled xe2x80x9cTIME DIVISION MULTIPLEXED SYNCHRONOUS STATE MACHINE HAVING STATE MEMORYxe2x80x9d), all except U.S. Pat. No. 5,809,032 filed on the same date as this application and which are hereby incorporated by reference.
1. Technical Field
This invention relates to digital circuitry and, more particularly, to a synchronous state machine.
2. Background of the Invention
A synchronous state machine is normally implemented with logic responsive to external inputs and the previous state of the state machine for providing the next state which is then stored for use in the next clock period. In some circumstances it is required that many different similar or identical logical functions be carried out simultaneously or one after another, e.g., where the external inputs are provided in the form of a time division multiplexed signal having a repeating pattern. In the latter case, we encountered a problem in which there was a need to replicate the logic for carrying out the state machine identically for a plurality of groups of signals that shared a common super group or frame and also a superframe. Since the signals in the groups were provided serially it was possible to contemplate how we might use the hardware we designed to carry out the state machine for each of the groups; in other words, we wanted to figure out how to avoid having to duplicate the logic many times, i.e., once for each group.
For example, in the synchronous optical network (SONET) standard there is defined a plurality of virtual tributaries (VT) or tributary units (TU) which may be used as subunits of a synchronous payload envelope (SPE) or virtual container (VC), respectively, in a synchronous transport signal (STS) or synchronous transport module (STM). In the U.S.A., for example, there may be up to twenty-eight VT 1.5 payloads received serially in seven groups, each having four VT 1.5s, at a network element in each repetitive frame of a 8 kHz frame structure with 27 bytes in each VT 1.5 with the remaining 54 bytes for overhead.
A network element that receives such a SONET signal requires processing all twenty-eight pointers on the high speed receive interface. We could have taken an approach of designing a single VT pointer processor and duplicated it twenty-eight times to provide this function. However, each such VT pointer processor would have had an associated cost to it in terms of gate count (approximately 2,000 gates plus elastic store) or area. Multiplying this function by twenty-eight would have a cost of approximately 48,000 gates plus elastic store. This is a very high cost in terms of today""s technology. But it was very problematic as to how to avoid replicating the logic since a time division multiplexing of a synchronous state machine was hard to even conceive of, let alone carry out.
An object of the present invention is to time division multiplex the logic or hardware used to implement a synchronous state machine.
According to the present invention, the logical function is implemented in hardware only once and is time division multiplexed by using a memory to hold the states of one or more state machines that have thus been duplicated. To provide access to the memory, only the flip-flop portion of the synchronous state machine needs to change. All flip-flops in any given synchronous state machine may be replaced with a substitution element, for routing the next state from the logical implementation for storage in memory until the next cycle and for receiving from memory a previous state for provision on the next cycle to the logical implementation.
This technique partitions one very complex problem into three very simple problems which can be controlled independently. First, the logical implementation can be specified, designed and verified from the point of view of one state machine. Second, the architecture which provides access to the memory can be achieved by one simple substitution circuit which is used to replace all of the flip-flops in the state machine implementation. Third, the design of the memory and access thereto can be independent of the function of the state machine and its architecture.
In the example given below for a SONET receive interface, by taking advantage of the fact that the bytes of the VT/TUs are time multiplexed, the logic portion of a VT/TU pointer processor can be shared by all VT/TU pointer processor functions and the state of each pointer processor, i.e., with respect to individual VTs or TUs, can be stored in a state memory. With this architecture, the cost is on the order of only 2,000 gates plus 16,000 gates of state RAM plus elastic store (approximately 18,000 gates plus elastic store). This is a savings of 30,000 gates in an application specific integrated circuit (ASIC). The savings are even greater in terms of area since the state memory will have better area utilization then would a totally replicative logical design.
These and other objects, features and advantages of the present invention will become more apparent in light of the following detailed description of a best mode embodiment thereof, as illustrated in the accompanying drawing.